package datastructure.ch01_base;

/**
 * 时间复杂度 & 空间复杂度
 * 时间复杂度：估算程序指令的执行次数（执行时间），大O表示法。
 * 空间复杂度：估算所需要占用的存储空间
 *
 * @author guodd
 * @version 1.0 use jdk 1.8
 */
public class ComplexityAnalysis {
    public static void test1(int n) {
        // 汇编指令 不等于 当前语言的指令

        // 1 + 1
        // 2
        if (n > 10) {
            System.out.println("n > 10");
        } else if (n > 5) { // 2
            System.out.println("n > 5");
        } else {
            System.out.println("n <= 5");
        }

        // 1 + 4 + 4 + 4 = 13
        for (int i = 0; i < 4; i++) {
            System.out.println("test");
        }

        // 只要是常量，不管多大，时间复杂度都是O(1)
        // 140000
        // O(1)
    }

    public static void test2(int n) {
        // 1 + n + n + n
        // 1+3n

        // 忽略常数、系数
        // O(n)
        for (int i = 0; i < n; i++) {
            System.out.println("test");
        }
    }

    public static void test3(int n) {
        // 1 + 2n + n * (1 + 3n)
        // 1 + 2n + n + 3n^2
        // 3n^2 + 3n + 1

        // 忽略低阶、常数、系数
        // O(n^2)
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                System.out.println("test");
            }
        }
    }

    public static void test4(int n) {
        // 1 + 2n + n * (1 + 45)
        // 1 + 2n + 46n
        // 48n + 1
        // O(n)
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < 15; j++) {
                System.out.println("test");
            }
        }
    }

    public static void test5(int n) {
        // 8 = 2^3
        // 16 = 2^4

        // 3 = log2(8)
        // 4 = log2(16)

        // 执行次数 = log2(n)
        // O(logn)
        while ((n = n / 2) > 0) {
            System.out.println("test");
        }
    }

    public static void test6(int n) {
        // log5(n)
        // O(logn)
        while ((n = n / 5) > 0) {
            System.out.println("test");
        }
    }

    public static void test7(int n) {
        // 1 + 2*log2(n) + log2(n) * (1 + 3n)

        // 1 + 3*log2(n) + 2 * nlog2(n)
        // O(nlogn)
        for (int i = 1; i < n; i = i * 2) {
            // 1 + 3n
            for (int j = 0; j < n; j++) {
                System.out.println("test");
            }
        }
    }

    public static void test10(int n) {
        // O(n)
        int a = 10;
        int b = 20;
        int c = a + b;
        int[] arrays = new int[n];
        for (int j : arrays) {
            System.out.println(j + c);
        }
    }
}
